package main

import (
	"fmt"
)

/*
二叉树的锯齿形层序遍历
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：
[
  [3],
  [20,9],
  [15,7]
]
 */

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	res := make([][]int, 0)
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	flag := -1
	rev := func(arr []int) []int {
		left, right := 0, len(arr) - 1
		for left < right {
			arr[left], arr[right] = arr[right], arr[left]
			left ++
			right --
		}
		return arr
	}
	for len(queue) > 0 {
		length := len(queue)
		temp := make([]int, 0)
		flag += 1
		for i := 0; i < length; i ++ {
			temp = append(temp, queue[i].Val)
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		if flag % 2 == 0 {
			res = append(res, temp)
		}else {
			// 翻转数组
			arr := rev(temp)
			res = append(res, arr)

		}
		queue = queue[length:]
	}

	return  res
}

func main() {
	root := &TreeNode{Val:3}
	root.Left = &TreeNode{Val:9}
	root.Right = &TreeNode{Val:20}
	root.Right.Left = &TreeNode{Val:15}
	root.Right.Right = &TreeNode{Val:7}

	fmt.Println(root)

	fmt.Println(zigzagLevelOrder(root))
}
